package com.demo.java.OD351_400.OD352;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【MELON 的难题(B卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146164088
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 输入雨花石的数量n
        int n = sc.nextInt();
        sc.nextLine(); // 读取换行符，准备读取下一行的输入

        // 输入每个雨花石的重量
        String input = sc.nextLine();
        List<Integer> nums = split(input); // 将输入的字符串转化为数字列表

        // 计算所有雨花石的总重量
        int sum = 0;
        for (int num : nums) {
            sum += num; // 累加所有的雨花石重量
        }

        // 如果总重量是奇数，无法平衡分配，直接输出 -1
        if (sum % 2 != 0) {
            System.out.println(-1);
            return; // 直接结束程序
        }

        // 计算目标重量（总重量的一半）
        int target = sum / 2;

        // 使用动态规划方法计算是否能够达到目标重量，并返回最少的雨花石数量
        int result = findMinCount(nums, n, target);

        // 如果找不到合适的分配方式，则输出 -1
        if (result == n) {
            System.out.println(-1);
        } else {
            // 输出能够平衡分配的最小雨花石数量
            System.out.println(result);
        }
    }

    // 将输入的字符串按空格拆分成数字列表
    private static List<Integer> split(String paramsStr) {
        String[] tokens = paramsStr.split(" "); // 按空格分割字符串
        List<Integer> result = new ArrayList<>();
        for (String token : tokens) {
            result.add(Integer.parseInt(token)); // 将字符串转为整数，并加入结果列表
        }
        return result;
    }

    // 使用动态规划方法计算最小的雨花石数量，使得总重量为target
    private static int findMinCount(List<Integer> nums, int n, int target) {
        // dp[i][j]表示使用前i块雨花石，是否能够凑成重量j
        int[][] dp = new int[n + 1][target + 1];

        // 初始化dp数组
        for (int i = 0; i <= target; i++) {
            dp[0][i] = n; // 如果没有任何雨花石，所有的重量都无法完成，设置为最大值n
        }

        // 动态规划填充dp数组
        for (int i = 1; i <= n; i++) {
            int num = nums.get(i - 1); // 获取第i块雨花石的重量
            for (int j = 1; j <= target; j++) {
                if (j < num) {
                    dp[i][j] = dp[i - 1][j]; // 如果当前目标重量j小于当前雨花石的重量，则不能选择当前雨花石，继承上一行的结果
                } else {
                    // 否则，可以选择当前雨花石，或者不选择当前雨花石，取二者中的较小值
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - num] + 1);
                }
            }
        }

        // 返回最终的结果
        return dp[n][target]; // 返回最少需要的雨花石数量
    }
}
